package kyssion.introductionToAlgorithms.chapter_06;

import kyssion.leetcode.util.ShowUtil;

public class Alorithms_6_001堆排序 {

    public static void main(String[] args) {
        int[] arr = new int[]{
                1, 6, 5, 7, 4, 3, 9, 8, 10, 17, 15
        };
        new Alorithms_6_001堆排序().heapSort(arr);
        ShowUtil.showArr(arr);
    }

    /**
     * 维护大顶堆堆的状态
     *
     * @param arr
     * @param index
     */
    public void maxHeapify(int[] arr, int index, int length) {
        int l = index * 2 + 1;       //left
        int r = (index + 1) * 2; //right
        int larger = index;
        if (l < length && arr[l] > arr[larger]) {
            larger = l;
        }

        if (r < length && arr[r] > arr[larger]) {
            larger = r;
        }

        if (larger != index) {
            exchange(arr, larger, index);
            maxHeapify(arr, larger, length);
        }
    }

    /**
     * 构建大顶堆
     * @param arr
     */
    public void buildMaxHeap(int[] arr) {
        int length = arr.length / 2;
        for (int a = length; a >= 0; a--) {
            maxHeapify(arr, a, arr.length);
        }
    }

    public void exchange(int[] arr, int a, int b) {
        int before = arr[a];
        arr[a] = arr[b];
        arr[b] = before;
    }

    //堆排序算法
    public void heapSort(int[] arr) {
        buildMaxHeap(arr);
        for (int a = arr.length - 1; a > 0; a--) {
            exchange(arr, a, 0);
            maxHeapify(arr, 0, a);
        }
    }

}
